/*
 * @lc app=leetcode.cn id=221 lang=javascript
 *
 * [221] 最大正方形
 */

// @lc code=start
/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalSquare = function (matrix) {
  const row = matrix.length;
  const col = matrix[0].length;
  const curMax = Array.from({ length: row }, () => new Array(col).fill(0));
  let maxEdge = 0;
  // 本题递归有个结论需要知道，当前格最大矩形边为左上三格最小值+1（前提本格不为0）
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      if (i === 0 || j === 0) {
        curMax[i][j] = Number(matrix[i][j]);
        maxEdge = Math.max(curMax[i][j], maxEdge);
        continue;
      }
      if (matrix[i][j] === "1") {
        curMax[i][j] =
          Math.min(curMax[i - 1][j], curMax[i - 1][j - 1], curMax[i][j - 1]) +
          1;
        maxEdge = Math.max(curMax[i][j], maxEdge);
      }
    }
  }
  return maxEdge * maxEdge;
};
// @lc code=end
